#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;

//#include<stdio.h>
//int main()
//{
//	static char* s[] = { "black","white", "pink", "violet" };
//	char** ptr[] = { s + 3, s + 2, s + 1, s }, *** p;
//	p = ptr;
//	++p;
//	printf("%s", **p + 1);
//	return 0;
//}

//class Solution {
//public:
//    bool CheckPermutation(string s1, string s2) {
//        if (s1.size() != s2.size())
//            return false;
//        int count1[26] = { 0 };
//        int count2[26] = { 0 };
//        for (auto ch : s1)
//        {
//            count1[ch - 'a']++;
//        }
//        for (auto ch : s2)
//        {
//            count2[ch - 'a']++;
//        }
//        for (int i = 0; i < 26; i++)
//        {
//            if (count1[i] != count2[i])
//            {
//                return false;
//            }
//        }
//        return true;
//    }
//};

#include <iostream>
using namespace std;
//
//int main()
//{
//    int n = 0;
//    cin >> n;
//    string s1;
//    while (n)
//    {
//        cin >> s1;
//        char* str;
//        str = itoa(s1.size(), str, 2);
//        if (s1.size() >= 10)
//        {
//            cout << *s1.begin();
//            cout << str;
//            cout << *(s1.begin() + s1.size()-1);
//        }
//        else
//        {
//            cout << s1.c_str() << endl;
//        }
//        n--;
//    }
//}

//class Solution {
//public:
//    static string replaceSpaces(string S, int length) {
//        string S1("");
//        for (int i = 0; i < length; i++)
//        {
//            if (S[i] == ' ')
//            {
//                S1 += "%20";
//            }
//            else
//            {
//                S1 += S[i];
//            }
//        }
//        return S1;
//    }
//};
//
//int main()
//{
//    Solution::replaceSpaces("Mr John Smith    ",13);
//}
//
//#include <string>
//class Solution {
//public:
//    static string compressString(string S) {
//        string S1("");
//        int count = 0;
//        S1 += *(S.begin());
//        char tmp = *(S.begin());
//        for (auto ch : S)
//        {
//            if (tmp != ch)
//            {
//                tmp = ch;
//                S1 += to_string(count);
//                S1 += ch;
//                count = 1;
//            }
//            else
//            {
//                count++;
//            }
//        }
//        S1+= to_string(count);
//        return S1.size() > S.size() ? S : S1;
//    }
//};
//int main()
//{
//    Solution::compressString("aabcccccaaa");
//    return 0;
//}

//int main()
//{
//	// 11
//	int num = 3;
//	int ret = (num & 0x55555555) << 1;
//	int ret1 = (num & 0xAAAAAAAA) >> 1;
//	return 0;
//}


//#include<stdio.h>
//char* f(char* str, char ch)
//{
//	char* it1 = str;
//	char* it2 = str;
//	while (*it2 != '\0')
//	{
//		while (*it2 == ch)
//		{
//			it2++;
//		}
//		*it1++ = *it2++;
//	}
//	return str;
//}
//int main() {
//	char a[10];
//	strcpy(a, "abcdcccd");
//	printf("%s", f(a, 'c'));
//	return 0;
//}

#include <iostream>
using namespace std;
int fun(int tmp)
{
    if (tmp == 1)
        return 1;
    if (tmp == 2)
        return 2;
    int a1 = 1;
    int a2 = 2;
    int a3 = 0;
    while (tmp > 2)
    {
        a3 = (a1 * 2 * a2)%32767;
        a1 = a2;
        a2 = a3;
        tmp--;
    }
    return a3;
}
int main()
{
    int n = 0;
    cin >> n;
    while (n)
    {
        int tmp = 0;
        cin >> tmp;
        cout << fun(tmp) << endl;
        n--;
    }
    return 0;
}